package leetcode.editor.cn.dsa24_dijkstra;
//有 N 个网络节点，标记为 1 到 N。
//
// 给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从
//源节点传递到目标节点的时间。 
//
// 现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。 
//
// 示例：
// 输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
//输出：2
// 
// 注意:
// N 的范围在 [1, 100] 之间。
// K 的范围在 [1, N] 之间。 
// times 的长度在 [1, 6000] 之间。 
// 所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。 
// 
// Related Topics 堆 深度优先搜索 广度优先搜索 图 
// 👍 212 👎 0


import java.util.ArrayList;
import java.util.PriorityQueue;

public class NetworkDelayTime743_2 {
    public static void main(String[] args) {
        Solution solution = new NetworkDelayTime743_2().new Solution();
        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        System.out.println(solution.networkDelayTime(times, 4, 2)); //2
        int[][] times2 = {{2,6,2},{2,5,8},{6,1,6},{6,4,2},{1,3,3},
                {3,7,2},{5,7,3},{4,1,3},{4,5,1},{4,3,1}};
        System.out.println(solution.networkDelayTime(times2, 7, 2)); //7
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int networkDelayTime(int[][] times, int N, int K) {
            // 构建有权图的邻接表adj
            ArrayList<ArrayList<int[]>> adj = new ArrayList<>(N+1);
            for (int i = 0; i <= N; i++) {
                adj.add(new ArrayList<>());
            }
            for (int i = 0; i < times.length; i++) {
                adj.get(times[i][0]).add(new int[]{times[i][1], times[i][2]});
            }
            int[] dist = new int[N+1]; // dist存储从源节点k到各个节点的最短距离
            for (int i = 0; i <= N; i++) {
                dist[i] = Integer.MAX_VALUE; // 初始化最短距离为无穷大
            }
            dist[K] = 0;
            // 存储已经选择的最短路径的顶点，即集合D
            boolean[] visited = new boolean[N+1];
            // 优先队列，存储待遍历的节点
            PriorityQueue<int[]> queue = new PriorityQueue<>(N, (o1, o2) -> {
                return o1[1] - o2[1];
            });
            queue.offer(new int[]{K, 0});
            while (!queue.isEmpty()) {
                int vert = queue.poll()[0];
                if (visited[vert]) continue;
                visited[vert] = true;
                // 更新当前顶点下所有邻居节点的最短路径
                ArrayList<int[]> list = adj.get(vert);
                for (int[] info : list) {
                    // 节点未被访问且新的路径比节点已有的最短距离更小
                    if (!visited[info[0]] && dist[info[0]] > dist[vert] + info[1]) {
                        // 先更新最短距离，再入队
                        dist[info[0]] = dist[vert] + info[1];
                        queue.offer(new int[]{info[0], dist[info[0]]});
                    }
                }
            }
            // 寻找最短路径中的最大值并返回
            int max = 0;
            for (int i = 1; i <= N; i++) {
                if (dist[i] == Integer.MAX_VALUE) return -1;
                max = Math.max(max, dist[i]);
            }
            return max;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}